#region File Description
//-----------------------------------------------------------------------------
// SpritePacker.cs
//
// Microsoft Game Technology Group
// Copyright (C) Microsoft Corporation. All rights reserved.
//-----------------------------------------------------------------------------
#endregion

#region Using Statements
using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;
#endregion

namespace SpriteSheetPipeline
{
	/// <summary>
	/// Helper for arranging many small sprites into a single larger sheet.
	/// </summary>
	public static class SpritePacker
	{
		/// <summary>
		/// Packs a list of sprites into a single big texture,
		/// recording where each one was stored.
		/// </summary>
		public static BitmapContent PackSprites(IList<BitmapContent> sourceSprites,
												ICollection<Rectangle> outputSprites,
												ContentProcessorContext context)
		{
			if (sourceSprites.Count == 0)
				throw new InvalidContentException("There are no sprites to arrange");

			// Build up a list of all the sprites needing to be arranged.
			List<ArrangedSprite> sprites = new List<ArrangedSprite>();

			for (int i = 0; i < sourceSprites.Count; i++)
			{
				ArrangedSprite sprite = new ArrangedSprite();

				// Include a single pixel padding around each sprite, to avoid
				// filtering problems if the sprite is scaled or rotated.
				sprite.Width = sourceSprites[i].Width + 2;
				sprite.Height = sourceSprites[i].Height + 2;

				sprite.Index = i;

				sprites.Add(sprite);
			}

			// Sort so the largest sprites get arranged first.
			sprites.Sort(CompareSpriteSizes);

			// Work out how big the output bitmap should be.
			int outputWidth = GuessOutputWidth(sprites);
			int outputHeight = 0;
			int totalSpriteSize = 0;

			// Choose positions for each sprite, one at a time.
			for (int i = 0; i < sprites.Count; i++)
			{
				PositionSprite(sprites, i, outputWidth);

				outputHeight = Math.Max(outputHeight, sprites[i].Y + sprites[i].Height);

				totalSpriteSize += sprites[i].Width * sprites[i].Height;
			}

			// Sort the sprites back into index order.
			sprites.Sort(CompareSpriteIndices);

			context.Logger.LogImportantMessage(
				"Packed {0} sprites into a {1}x{2} sheet, {3}% efficiency",
				sprites.Count, outputWidth, outputHeight,
				totalSpriteSize * 100 / outputWidth / outputHeight);

			return CopySpritesToOutput(sprites, sourceSprites, outputSprites,
									   outputWidth, outputHeight);
		}


		/// <summary>
		/// Once the arranging is complete, copies the bitmap data for each
		/// sprite to its chosen position in the single larger output bitmap.
		/// </summary>
		static BitmapContent CopySpritesToOutput(List<ArrangedSprite> sprites,
												 IList<BitmapContent> sourceSprites,
												 ICollection<Rectangle> outputSprites,
												 int width, int height)
		{
			BitmapContent output = new PixelBitmapContent<Color>(width, height);

			foreach (ArrangedSprite sprite in sprites)
			{
				BitmapContent source = sourceSprites[sprite.Index];

				int x = sprite.X;
				int y = sprite.Y;

				int w = source.Width;
				int h = source.Height;

				// Copy the main sprite data to the output sheet.
				BitmapContent.Copy(source, new Rectangle(0, 0, w, h),
								   output, new Rectangle(x + 1, y + 1, w, h));

				// Copy a border strip from each edge of the sprite, creating
				// a one pixel padding area to avoid filtering problems if the
				// sprite is scaled or rotated.
				BitmapContent.Copy(source, new Rectangle(0, 0, 1, h),
								   output, new Rectangle(x, y + 1, 1, h));

				BitmapContent.Copy(source, new Rectangle(w - 1, 0, 1, h),
								   output, new Rectangle(x + w + 1, y + 1, 1, h));

				BitmapContent.Copy(source, new Rectangle(0, 0, w, 1),
								   output, new Rectangle(x + 1, y, w, 1));

				BitmapContent.Copy(source, new Rectangle(0, h - 1, w, 1),
								   output, new Rectangle(x + 1, y + h + 1, w, 1));

				// Copy a single pixel from each corner of the sprite,
				// filling in the corners of the one pixel padding area.
				BitmapContent.Copy(source, new Rectangle(0, 0, 1, 1),
								   output, new Rectangle(x, y, 1, 1));

				BitmapContent.Copy(source, new Rectangle(w - 1, 0, 1, 1),
								   output, new Rectangle(x + w + 1, y, 1, 1));

				BitmapContent.Copy(source, new Rectangle(0, h - 1, 1, 1),
								   output, new Rectangle(x, y + h + 1, 1, 1));

				BitmapContent.Copy(source, new Rectangle(w - 1, h - 1, 1, 1),
								   output, new Rectangle(x + w + 1, y + h + 1, 1, 1));

				// Remember where we placed this sprite.
				outputSprites.Add(new Rectangle(x + 1, y + 1, w, h));
			}

			return output;
		}


		/// <summary>
		/// Internal helper class keeps track of a sprite while it is being arranged.
		/// </summary>
		class ArrangedSprite
		{
			public int Index;

			public int X;
			public int Y;

			public int Width;
			public int Height;
		}


		/// <summary>
		/// Works out where to position a single sprite.
		/// </summary>
		static void PositionSprite(List<ArrangedSprite> sprites,
								   int index, int outputWidth)
		{
			int x = 0;
			int y = 0;

			while (true)
			{
				// Is this position free for us to use?
				int intersects = FindIntersectingSprite(sprites, index, x, y);

				if (intersects < 0)
				{
					sprites[index].X = x;
					sprites[index].Y = y;

					return;
				}

				// Skip past the existing sprite that we collided with.
				x = sprites[intersects].X + sprites[intersects].Width;

				// If we ran out of room to move to the right,
				// try the next line down instead.
				if (x + sprites[index].Width > outputWidth)
				{
					x = 0;
					y++;
				}
			}
		}


		/// <summary>
		/// Checks if a proposed sprite position collides with anything
		/// that we already arranged.
		/// </summary>
		static int FindIntersectingSprite(List<ArrangedSprite> sprites,
										  int index, int x, int y)
		{
			int w = sprites[index].Width;
			int h = sprites[index].Height;

			for (int i = 0; i < index; i++)
			{
				if (sprites[i].X >= x + w)
					continue;

				if (sprites[i].X + sprites[i].Width <= x)
					continue;

				if (sprites[i].Y >= y + h)
					continue;

				if (sprites[i].Y + sprites[i].Height <= y)
					continue;

				return i;
			}

			return -1;
		}


		/// <summary>
		/// Comparison function for sorting sprites by size.
		/// </summary>
		static int CompareSpriteSizes(ArrangedSprite a, ArrangedSprite b)
		{
			int aSize = a.Height * 1024 + a.Width;
			int bSize = b.Height * 1024 + b.Width;

			return bSize.CompareTo(aSize);
		}


		/// <summary>
		/// Comparison function for sorting sprites by their original indices.
		/// </summary>
		static int CompareSpriteIndices(ArrangedSprite a, ArrangedSprite b)
		{
			return a.Index.CompareTo(b.Index);
		}


		/// <summary>
		/// Heuristic guesses what might be a good output width for a list of sprites.
		/// </summary>
		static int GuessOutputWidth(List<ArrangedSprite> sprites)
		{
			// Gather the widths of all our sprites into a temporary list.
			List<int> widths = new List<int>();

			foreach (ArrangedSprite sprite in sprites)
			{
				widths.Add(sprite.Width);
			}

			// Sort the widths into ascending order.
			widths.Sort();

			// Extract the maximum and median widths.
			int maxWidth = widths[widths.Count - 1];
			int medianWidth = widths[widths.Count / 2];

			// Heuristic assumes an NxN grid of median sized sprites.
			int width = medianWidth * (int)Math.Round(Math.Sqrt(sprites.Count));

			// Make sure we never choose anything smaller than our largest sprite.
			return Math.Max(width, maxWidth);
		}
	}
}
